//
// Description: 最长递增子序列模板
// Created by Loading on 2021/7/31.
//

/* 用于求解 一个数组中最长递增子序列（无需连续子序列且严格递增）的序列长度 */
/* 贪心 + 二分算法 要优于 动态规划 */

// 例题：300. 最长递增子序列
//      5841. 找出到每个位置为止最长的有效障碍赛跑路线

#include <bits/stdc++.h>

using namespace std;

/* 贪心 + 二分 ，时间复杂度：O(nlogn) */
int lengthOfLIS(vector<int> &nums) {
    // 最长递增子序列数组
    vector<int> maxLen_increase;

    for (auto &x : nums) {
        // 二分查找 在最长递增子序列数组中，第一个大于等于当前元素的位置
        auto it = lower_bound(maxLen_increase.begin(), maxLen_increase.end(), x);
        if (it != maxLen_increase.end()) {
            // 找到位置，贪心更新当前位置为更小的值
            *it = x;
        } else {
            // 未找到，直接追加
            maxLen_increase.emplace_back(x);
        }
    }

    return (int) maxLen_increase.size();
}

/* 动态规划 ，时间复杂度：O(n2) */
int lengthOfLIS_DP(vector<int> &nums) {
    // dp数组，dp[i] 表示以 i 结尾的最长递增子序列长度
    vector<int> dp(nums.size());

    for (int i = 0; i < nums.size(); ++i) {
        dp[i] = 1;
        // 遍历从开头到当前位置的元素
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                // dp 数组更新，取较大值
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {

}